package mht.practice.sort;

/**
 * 选择排序法
 * Created by MHT on 2017/8/25.
 */
public class SelectionSort {

    // 我们的算法类不允许产生任何实例
    private SelectionSort(){}

    //数组中两个元素进行位置交换
    private static void swap(Object arr[],int i,int j){
        Object temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void sort(Comparable arr[]){

        int n = arr.length;
        for (int i=0;i<n;i++){
            // 寻找[i, n)区间里的最小值的索引
            int minIndex = i;
            for (int j=i+1;j<n;j++){
                //使用compareTo方法比较两个Comparable对象的大小
                if (arr[j].compareTo(arr[minIndex]) < 0)
                    minIndex = j;


                    swap(arr,i,minIndex);
            }
        }
    }

    public static void main(String[] args) {

        //基本数组测试
        Comparable[] a = {1234,912,844,753,623,510,455,326,210,110};
        SelectionSort.sort(a);
        for (int i=0;i<a.length;i++){
            System.out.print(a[i]+"  ");
        }
        System.out.println();


//        int N = 20000;
//        Integer[] b = SortTestHelper.generateRandomArray(N,0,100000);
//        SortTestHelper.testSort("mht.practice.sort.SelectionSort",b);

    }
}
